% abstract.tex (Abstract)

\addcontentsline{toc}{chapter}{Abstract}

\chapter*{Abstract}

There are always two naive ways of breaking a block cipher, if no known weakness exists in it. One is the brute force attack, which requires availability of tremendous computational speed in order to try all possible keys. Other is the precomputed ciphertext attack, which imposes huge requirements on memory for storing ciphertext corresponding to all possible keys. Considering these extreme requirements, a middle way was proposed by Hellman called time-memory tradeoff (TMTO) attack. This attack reduces the requirement of time and memory to feasible domains making it possible to break ciphers under normal computational speed and memory, like using personal computers. The tradeoff is realized by storing a limited number of ciphertexts in memory selected by precomputing the Hellman tables.

TMTO attacks were first proposed on stream ciphers by Babbage and Golic. The principle of TMTO attack for stream cipher differs from that for block cipher due to the much different functional working between them. The goal in the Babbage-Golic attack is to find atleast one occurring value of the internal state while the keystream is generated. This is done by matching fixed length subsequences of the keystream with precomputed output of same length from states stored in memory. This forms the basic principle for tradeoff attacks on stream ciphers. 

In the first part of the thesis, we have implemented the Babbage-Golic attacks on the HiTag2 stream cipher. HiTag2 was a proprietary algorithm designed by Philips and kept secret until recently the algorithm was reverse-engineered from its silicon implementation. Two different attacks are mounted on this cipher based on different assumptions on the availability of keystream and their results are presented. 

Precomputation structure of the Hellman tables was modified by Biryukov and Shamir to apply on stream ciphers. They termed this attack as time-memory-data tradeoff (TMDTO) attack using Hellman tables. Further, an improvement of Hellman tables was proposed by Oechslin which reduces the attack time by a factor of two and considerably solves the problem of collisions in Hellman tables. The precomputation structure by Oechslin is called rainbow table. Later, Erguler and Anarim proposed modifications to the rainbow table in order to apply them on stream ciphers (called TMDTO attack using rainbow table).

In the later part of the thesis, we have implemented both the TMDTO attacks using Hellman and rainbow tables on HiTag2. The parameters which define the table structures are varied for both the tables and the results are presented. Further, we make a brief comparison between the proposals by Biryukov-Shamir and Erguler-Anarim, allowing us to see the performance of both these table structures for the same parameters. The results from the subsequent experiments performed with this implementation show the advantage of using rainbow table over Hellman tables.